Set matrix zeroes¶
Time: O(MN); Space: O(1); medium
Given a M x N matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Example 1:
Input: matrix =
[
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
Output:
[
[1, 0, 1],
[0, 0, 0],
[1, 0, 1]
]
Example 2: Input: matrix =
[
[0, 1, 2, 0],
[3, 4, 5, 2],
[1, 3, 1, 5]
]
Output:
[
[0, 0, 0, 0],
[0, 4, 5, 0],
[0, 3, 1, 0]
]
Follow up:
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
Hints:
If any cell of the matrix has a zero we can record its row and column number using additional memory. But if you don’t want to use extra memory then you can manipulate the array instead. i.e. simulating exactly what the question says.
Setting cell values to zero on the fly while iterating might lead to discrepancies. What if you use some other integer value as your marker? There is still a better approach for this problem with 0(1) space.
We could have used 2 sets to keep a record of rows/columns which need to be set to zero. But for an O(1) space solution, you can use one of the rows and and one of the columns to keep track of this information.
We can use the first cell of every row and column as a flag. This flag would determine whether a row or column has been set to zero.
Solution¶
The question seems to be pretty simple but the trick here is that we need to modify the given matrix in place i.e. our space complexity needs to O(1). We will go through three different approaches to the question. The first approach makes use of additional memory while the other two don’t.
1. Additional Memory Approach¶
Intuition If any cell of the matrix has a zero we can record its row and column number. All the cells of this recorded row and column can be marked zero in the next iteration.
Algorithm We make a pass over our original array and look for zero entries. If we find that an entry at [i, j] is 0, then we need to record somewhere the row i and column j. So, we use two sets, one for the rows and one for the columns. if cell[i][j] == 0: row_set.add(i) column_set.add(j) Finally, we iterate over the original matrix. } For every cell we check if the row r or column c had been marked earlier. } If any of them was marked, we set the value in the cell to 0. if r in row_set or c in column_set: cell[r][c] = 0
[8]:
class Solution1(object):
"""
Time: O(M x N), where M and N are the number of rows and columns respectively.
Space: O(M + N).
"""
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
R = len(matrix)
C = len(matrix[0])
rows, cols = set(), set()
# Essentially, we mark the rows and columns that are to be made zero
for i in range(R):
for j in range(C):
if matrix[i][j] == 0:
rows.add(i)
cols.add(j)
# Iterate over the array once again and using the rows and cols sets, update the elements
for i in range(R):
for j in range(C):
if i in rows or j in cols:
matrix[i][j] = 0
[9]:
s = Solution1()
matrix = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
s.setZeroes(matrix)
assert matrix == [
[1, 0, 1],
[0, 0, 0],
[1, 0, 1]
]
matrix = [
[0, 1, 2, 0],
[3, 4, 5, 2],
[1, 3, 1, 5]
]
s.setZeroes(matrix)
assert matrix == [
[0, 0, 0, 0],
[0, 4, 5, 0],
[0, 3, 1, 0]
]
2. O(1) Space, Efficient Solution¶
Intuition The inefficiency in the second approach is that we might be repeatedly setting a row or column even if it was set to zero already. We can avoid this by postponing the step of setting a row or a column to zeroes.
We can rather use the first cell of every row and column as a flag. This flag would determine whether a row or column has been set to zero. This means for every cell instead of going to M+NM+N cells and setting it to zero we just set the flag in two cells. if cell[i][j] == 0: cell[i][0] = 0 cell[0][j] = 0 These flags are used later to update the matrix. If the first cell of a row is set to zero this means the row should be marked zero. If the first cell of a column is set to zero this means the column should be marked zero.
Algorithm 1. We iterate over the matrix and we mark the first cell of a row i and first cell of a column j, if the condition in the pseudo code above is satisfied. i.e. if cell[i][j] == 0.
The first cell of row and column for the first row and first column is the same i.e. cell[0]. Hence, we use an additional variable to tell us if the first column had been marked or not and the cell[0] would be used to tell the same for the first row.
Now, we iterate over the original matrix starting from second row and second column i.e. matrix[1] onwards. For every cell we check if the row r or column c had been marked earlier by checking the respective first row cell or first column cell. If any of them was marked, we set the value in the cell to 0. Note the first row and first column serve as the row_set and column_set that we used in the first approach.
We then check if cell[0][0] == 0, if this is the case, we mark the first row as zero.
And finally, we check if the first column was marked, we make all entries in it as zeros.
We iterate all the cells and mark the corresponding first row/column cell incase of a cell with zero value.
We iterate the matrix we got from the above steps and mark respective cells zeroes.
[10]:
class Solution2(object):
"""
O(1) Space, Efficient Solution
Time: O(M x N)
Space: O(1)
"""
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
is_col = False
R = len(matrix)
C = len(matrix[0])
for i in range(R):
# Since first cell for both first row and first column is the same i.e. matrix[0][0]
# We can use an additional variable for either the first row/column.
# For this solution we are using an additional variable for the first column
# and using matrix[0][0] for the first row.
if matrix[i][0] == 0:
is_col = True
for j in range(1, C):
# If an element is zero, we set the first element of the corresponding row and column to 0
if matrix[i][j] == 0:
matrix[0][j] = 0
matrix[i][0] = 0
# Iterate over the array once again and using the first row and first column, update the elements.
for i in range(1, R):
for j in range(1, C):
if not matrix[i][0] or not matrix[0][j]:
matrix[i][j] = 0
# See if the first row needs to be set to zero as well
if matrix[0][0] == 0:
for j in range(C):
matrix[0][j] = 0
# See if the first column needs to be set to zero as well
if is_col:
for i in range(R):
matrix[i][0] = 0
[11]:
s = Solution2()
matrix = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
s.setZeroes(matrix)
assert matrix == [
[1, 0, 1],
[0, 0, 0],
[1, 0, 1]
]
matrix = [
[0, 1, 2, 0],
[3, 4, 5, 2],
[1, 3, 1, 5]
]
s.setZeroes(matrix)
assert matrix == [
[0, 0, 0, 0],
[0, 4, 5, 0],
[0, 3, 1, 0]
]
[12]:
import functools
class Solution3(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None # Do not return anything, modify matrix in-place instead.
"""
first_col = functools.reduce(lambda acc, i: acc or matrix[i][0] == 0, range(len(matrix)), False)
first_row = functools.reduce(lambda acc, j: acc or matrix[0][j] == 0, range(len(matrix[0])), False)
for i in range(1, len(matrix)):
for j in range(1, len(matrix[0])):
if matrix[i][j] == 0:
matrix[i][0], matrix[0][j] = 0, 0
for i in range(1, len(matrix)):
for j in range(1, len(matrix[0])):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if first_col:
for i in range(len(matrix)):
matrix[i][0] = 0
if first_row:
for j in range(len(matrix[0])):
matrix[0][j] = 0
[13]:
s = Solution3()
matrix = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
s.setZeroes(matrix)
assert matrix == [
[1, 0, 1],
[0, 0, 0],
[1, 0, 1]
]
matrix = [
[0, 1, 2, 0],
[3, 4, 5, 2],
[1, 3, 1, 5]
]
s.setZeroes(matrix)
assert matrix == [
[0, 0, 0, 0],
[0, 4, 5, 0],
[0, 3, 1, 0]
]